package com.spring.mvc.aigorithm;

public class Sort {

	public static void insert_sort(int[] array){
		for (int i = 1; i < array.length; i++) {
			int key=array[i];
			int j=i-1;
			while(j>=0 && array[j]>key){
				array[j+1]=array[j];
				j--;
			}
			array[j+1]=key;
		}
	}
	
	public static void merge_sort(int[] array,int p,int r){
		if(p<r){
			int q=(p+r)/2;
			merge_sort(array,p,q);
			merge_sort(array,q+1,r);
			merge(array,p,q,r);
		}
	}
	
	private static void merge(int[] array, int p, int q, int r) {
		int n1=q-p+1;
		int n2=r-q;
		int[] L=new int[n1+1];
		int[] R=new int[n2+1];
		for (int i = 0; i < n1; i++) {
			L[i]=array[p+i];
		}
		for (int i = 0; i < n2; i++) {
			R[i]=array[q+1+i];
		}
		L[n1]=(1<<31)-1;
		R[n2]=(1<<31)-1;
		
		int i=0,j=0;
		for (int k = p; k < r+1; k++) {
			if(L[i]<=R[j]){
				array[k]=L[i];
				i++;
			}else{
				array[k]=R[j];
				j++;
			}
		}
	}

	public static void main(String[] args) {
		int array[]={2,1,5,3,4,7,6};
		//insert_sort(array);
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i]+"\t");
		}
		System.out.println();
		merge_sort(array, 0, 6);
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i]+"\t");
		}
	}
}
